#include <stdio.h>
#include <stdlib.h>

int Josephus1(int n, int m) {
    int p = 0; // f(1) = 0

    // f(n) = (f(n - 1) + m) % n
    for(int i=2; i<=n; i++) {
        p = (p+m) % i;
    }
    return p + 1; // 索引加1
}

// 返回的是索引
// seq： 第几个人出局就传几
int Josephus2(int n, int m, int seq) {
    if (seq == 1)
        return (n + m - 1) % n;
    else
        return (Josephus2(n - 1, m, seq - 1) + m) % n;
}

// 递归版本返回的是索引
int Josephus4(int n, int m) {
    return n > 1 ? (Josephus4(n - 1, m) + m) % n : 0;
}

typedef struct Node {
    int data;
    struct Node* next;
} Node, *LinkedList;

int Josephus3(int n, int m) {
    LinkedList list, head, curr, tmp;
    head = NULL;

    for (int i = 0; i < n; i++) {
        tmp = (Node*)calloc(1, sizeof(Node));
        tmp->data = i + 1;
        if (!head) {
            head = tmp;
        } else {
            curr->next = tmp;
        }
        curr = tmp;
    }
    curr->next = head;
    list = head;
    Node* prev = NULL;
    int target = -1;

    for (int i = 0; i < n; i++) {
        // curr当前报数的节点, prev是curr的前一个节点, 为了删除curr用
        for (int j = 0; j < m; j++, prev = curr, curr = curr->next)
            ;
        // printf("%d-%d\n", i + 1, curr->data);
        if (i == n - 1) {
            target = curr->data;
            break;
        }
        prev->next = curr->next; // 删除报"m"的那个人
    }

    curr = list;
    for (int i = 0; i < n; i++) {
        tmp = curr->next;
        free(curr);
        curr = tmp;
    }
    list = NULL;
    return target;
}

int main(int argc, char const *argv[])
{
    int n = 41;
    int m = 3;
    printf("%d \n", Josephus1(n, m));
    printf("%d \n", Josephus2(n, m, n) + 1);
    printf("%d \n", Josephus3(n, m));
    printf("%d \n", Josephus4(n, m) + 1);
    return 0;
}
